# def InsetSort(num):
#     if len(num)==0:
#         return num
#     for i in range(len(num)-1): #循环N次
#         #1 3 4 2 i=2
#         #if num[i]>num[i+1]:#num[i+1]不合理，寻找num[i+1]的插入位置,从后往前找小的数，
#         InsetIndex=i
#         needmove=num[i+1]
#         while(InsetIndex>=0 and needmove<num[InsetIndex]):#循环1 2 3 5 6 7  .。。。1/2*n^2
#             num[InsetIndex+1]=num[InsetIndex]
#             InsetIndex=InsetIndex-1
#         num[InsetIndex+1]=needmove
#     print(num)
#
# if __name__=='__main__':
#     nums=[1,5,3,9,4,58,12]
#     print(nums)
#     InsetSort(nums)


def InsertSort(num:list):
    if len(num)==0:
        return num
    else:
        for i in range(len(num)-1):  #循环n-1
            # 2 3 4 1 i=2
            current=i
            behind=current+1
            # loop_count=0
            #因为i是外循环变量，所以用一个零时变量InsertPosition代替，始终是当前数和后面的数（两个数比较，再交换位置）
            while(num[current]>num[behind] and current>=0): #behind前面有current个数，最多循环current次，也就是n-1次
                #交换4与2的位置
                behind_Value=num[behind]
                num[behind]=num[current]
                num[current]=behind_Value
                #逐渐和前面的数进行比较
                current=current-1
                behind = current + 1
                # loop_count=loop_count+1
            print(num)

if __name__=='__main__':
    nums=[2,3,4,1]
    InsertSort(nums)
